#ifndef __SET_OF_STACKS_H__
#define __SET_OF_STACKS_H__

#include "global.h"

template <class Type>
struct HEAD_LINK_LIST {
	NODE<Type> *head;
	NODE<Type> *tail;
	size_t node_num;
	HEAD_LINK_LIST *next;
	HEAD_LINK_LIST *prev;
};

#define STACK_SIZE 30

template <class Type>
class SetOfStack {
public:
	SetOfStack();
	~SetOfStack();

	bool push(Type val);
	bool pop();
	Type top();
	bool popAt(size_t stack_no);
	Type topAt(size_t stack_no);

	bool empty();
	size_t size();
	size_t getSubStackNum();

private:
	bool removeAllNodes(NODE<Type> *head);
	bool addNode(NODE<Type> *&head, 
				 NODE<Type> *&tail, 
				 Type val);
	
	size_t stack_num;
	HEAD_LINK_LIST<Type> *head_ll;
	HEAD_LINK_LIST<Type> *tail_ll;
	NODE<Type> *head;
};

template <class Type>
SetOfStack<Type>::SetOfStack() {
	stack_num = 0;
	head_ll = NULL;
	tail_ll = NULL;
	head = NULL;
}

template <class Type>
bool SetOfStack<Type>::removeAllNodes(NODE<Type> *head) {
	NODE<Type> *node, *tmp_node;
	node = head;
	while (node) {
		tmp_node = node;
		node = node->next;
		free(tmp_node);
	}

	return true;
}

template <class Type>
bool SetOfStack<Type>::addNode(NODE<Type> *&head, 
			 NODE<Type> *&tail, 
			 Type val) {
	NODE<Type> *node = (NODE<Type> *)malloc(sizeof(NODE<Type>));
	if (node == NULL) {
		cout << "Allocate node buffer error, NULL!" << endl;
		return false;
	}

	memset(node, 0, sizeof(NODE<Type>));
	node->val = val;

	// First node in the substack
	if (head == NULL) {
		head = tail = node;
	}
	else {
		node->next = head;
		head->prev = node;
		head = node;
	}

	return true;
}
	
template <class Type>
SetOfStack<Type>::~SetOfStack() {
	HEAD_LINK_LIST<Type> *node, *tmp_node;
	node = head_ll;
	while (node) {
		tmp_node = node;
		if (!removeAllNodes(node->head)) {
			cout << "Remove stack error!" << endl;
		}
		node = node->next;
		free(tmp_node);
	}
}

template <class Type>
bool SetOfStack<Type>::push(Type val) {
	// empty stack now, create a new stack
	HEAD_LINK_LIST<Type> *head_node;
	if (head_ll == NULL) {
		head_node = (HEAD_LINK_LIST<Type> *)malloc(sizeof(HEAD_LINK_LIST<Type>));
		if (head_node == NULL) {
			cout << "Allocate head node error, NULL!" << endl;
			return false;
		}
		memset(head_node, 0, sizeof(HEAD_LINK_LIST<Type>));
		head_ll = tail_ll = head_node;
		++stack_num;
	}
	else {
		// check whether the last stack is full
		// if full, create a new sack
		if (head_ll->node_num >= STACK_SIZE) {
			HEAD_LINK_LIST<Type> *head_node;
			head_node = (HEAD_LINK_LIST<Type> *)malloc(sizeof(HEAD_LINK_LIST<Type>));
			if (head_node == NULL) {
				cout << "Allocate head node error, NULL!" << endl;
				return false;
			}
			memset(head_node, 0, sizeof(HEAD_LINK_LIST<Type>));
			head_node->next = head_ll;
			head_ll->prev = head_node;
			head_ll = head_node;
			++stack_num;
		}
	}

	if (!addNode(head_ll->head, head_ll->tail, val)) {
		cout << "Add not to stack error" << endl;
		return false;
	}
	// add 1 to the number of nodes in the stack
	++head_ll->node_num;

	return true;
}

template <class Type>
Type SetOfStack<Type>::top() {
	if (head_ll == NULL) {
		cout << "Error, empty stack!" << endl;
		return (Type)0;
	}
	
	if (head_ll->head == NULL) {
		cout << "Error, empty substack!" << endl;
		return (Type)0;
	}

	return head_ll->head->val;
}

template <class Type>
bool SetOfStack<Type>::pop() {
	if (head_ll == NULL) {
		cout << "Error, empty stack!" << endl;
		return false;
	}

	if (head_ll->head == NULL) {
		cout << "Error, empty substack!" << endl;
		return false;
	}

	NODE<Type> *node = head_ll->head;
	head_ll->head = node->next;
	free(node);
	--head_ll->node_num;
	// If the substack becomes empty, remove the
	// substack
	if (head_ll->node_num == 0) {
		// current substack is the last substack
		if (head_ll == tail_ll) {
			free(head_ll);
			head_ll = tail_ll = NULL;
		}
		else {
			HEAD_LINK_LIST<Type> *head_node;
			head_node = head_ll;
			head_ll = head_node->next;
			free(head_node);
		}
		--stack_num;
	}

	return true;
}

template <class Type>
bool SetOfStack<Type>::empty() {
	if (head_ll == NULL) {
		return true;
	}
	else {
		return false;
	}
}

template <class Type>
size_t SetOfStack<Type>::size() {
	HEAD_LINK_LIST<Type> *head_node;
	size_t total_node_num = 0;
	head_node = head_ll;
	while (head_node) {
		total_node_num += head_node->node_num;
		head_node = head_node->next;
	}

	return total_node_num;
}

template <class Type>
size_t SetOfStack<Type>::getSubStackNum() {
	return stack_num;
}

template <class Type>
Type SetOfStack<Type>::topAt(size_t stack_no) {
	size_t stack_index = 0;
	HEAD_LINK_LIST<Type> *head_node = tail_ll;
	while (head_node && stack_index < stack_no) {
		head_node = head_node->prev;
		++stack_index;
	}

	if (head_node == NULL) {
		cout << "Stack contains less than " << stack_no << " of substacks" << endl;
		return (Type)0;
	}

	if (head_node->head == NULL) {
		cout << "Substack is empty!" << endl;
		return (Type)0;
	}

	return head_node->head->val;
}

template <class Type>
bool SetOfStack<Type>::popAt(size_t stack_no) {
	size_t stack_index = 0;
	HEAD_LINK_LIST<Type> *head_node = tail_ll;
	while (head_node && stack_index < stack_no) {
		head_node = head_node->prev;
		++stack_index;
	}
	if (head_node == NULL) {
		cout << "Stack contains less than " << stack_no << " of substacks!" << endl;
		return (Type)0;
	}

	if (head_node->head == NULL) {
		cout << "Substack is empty!" << endl;
		return (Type)0;
	}

	NODE<Type> *node = head_node->head;
	head_node->head = head_node->head->next;
	--head_node->node_num;
	// If the current substack becomes empty
	if (head_node->node_num == 0) {
		if (head_ll == tail_ll) {
			free(head_ll);
			head_ll = tail_ll = NULL;
		}
		else {
			head_ll = head_node->next;
			free(head_node);
		}
		--stack_num;
	}
	else {
		// If it is full, move the last elem to the head of head_node
		while (head_node->prev) {
			HEAD_LINK_LIST<Type> *head_prev;
			head_prev = head_node->prev;
			node = head_prev->tail;
			head_prev->tail = node->prev;
			--head_prev->node_num;
			if (head_prev->node_num == 0) {
				head_node->prev = NULL;
				head_ll = head_node;
				
				free(head_prev);
				--stack_num;
				break;
			}

			node->next = head_node->head;
			node->prev = NULL;
			head_node->head->prev = node;
			head_node->head = node;
			++head_node->node_num;
	
			head_node = head_prev;
		}
	}
		
	return true;
}

#endif

